{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Evaluate Reverse Polish Notation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: evalRPN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #逆波兰表达式求值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串数组 <code>tokens</code> ，表示一个根据&nbsp;<a href=\"https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437\" target=\"_blank\">逆波兰表示法</a> 表示的算术表达式。</p>\n",
    "\n",
    "<p>请你计算该表达式。返回一个表示表达式值的整数。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>有效的算符为 <code>'+'</code>、<code>'-'</code>、<code>'*'</code> 和 <code>'/'</code> 。</li>\n",
    "\t<li>每个操作数（运算对象）都可以是一个整数或者另一个表达式。</li>\n",
    "\t<li>两个整数之间的除法总是 <strong>向零截断</strong> 。</li>\n",
    "\t<li>表达式中不含除零运算。</li>\n",
    "\t<li>输入是一个根据逆波兰表示法表示的算术表达式。</li>\n",
    "\t<li>答案及所有中间计算结果可以用 <strong>32 位</strong> 整数表示。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tokens = [\"2\",\"1\",\"+\",\"3\",\"*\"]\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tokens = [\"4\",\"13\",\"5\",\"/\",\"+\"]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tokens = [\"10\",\"6\",\"9\",\"3\",\"+\",\"-11\",\"*\",\"/\",\"*\",\"17\",\"+\",\"5\",\"+\"]\n",
    "<strong>输出：</strong>22\n",
    "<strong>解释：</strong>该算式转化为常见的中缀算术表达式为：\n",
    "  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5\n",
    "= ((10 * (6 / (12 * -11))) + 17) + 5\n",
    "= ((10 * (6 / -132)) + 17) + 5\n",
    "= ((10 * 0) + 17) + 5\n",
    "= (0 + 17) + 5\n",
    "= 17 + 5\n",
    "= 22</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= tokens.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>tokens[i]</code>&nbsp;是一个算符（<code>\"+\"</code>、<code>\"-\"</code>、<code>\"*\"</code> 或 <code>\"/\"</code>），或是在范围 <code>[-200, 200]</code> 内的一个整数</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>逆波兰表达式：</strong></p>\n",
    "\n",
    "<p>逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>平常使用的算式则是一种中缀表达式，如 <code>( 1 + 2 ) * ( 3 + 4 )</code> 。</li>\n",
    "\t<li>该算式的逆波兰表达式写法为 <code>( ( 1 2 + ) ( 3 4 + ) * )</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>逆波兰表达式主要有以下两个优点：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>去掉括号后表达式无歧义，上式即便写成 <code>1 2 + 3 4 + * </code>也可以依据次序计算出正确结果。</li>\n",
    "\t<li>适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [evaluate-reverse-polish-notation](https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [evaluate-reverse-polish-notation](https://leetcode.cn/problems/evaluate-reverse-polish-notation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"2\",\"1\",\"+\",\"3\",\"*\"]', '[\"4\",\"13\",\"5\",\"/\",\"+\"]', '[\"10\",\"6\",\"9\",\"3\",\"+\",\"-11\",\"*\",\"/\",\"*\",\"17\",\"+\",\"5\",\"+\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from operator import add, sub, mul\n",
    "class Solution:\n",
    "    operator_map = {\n",
    "        '+': add,\n",
    "        '-': sub,\n",
    "        '*': mul,\n",
    "        '/': lambda x, y: int(x / y) \n",
    "        #int(x / y)：朝着0的方向取整\n",
    "    }\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for i in tokens:\n",
    "            if i not in {'+','-','*','/'}:\n",
    "                stack.append(int(i)) # 要用int（否则就是str），不然后续没法计算\n",
    "            else:\n",
    "                b = stack.pop()\n",
    "                a = stack.pop()\n",
    "                ans = self.operator_map[i](a,b) # int\n",
    "                stack.append(ans)\n",
    "        return stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        \"\"\"\n",
    "        :type tokens: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not tokens:\n",
    "            return 0\n",
    "        stack = []\n",
    "        for i in tokens:\n",
    "            try:\n",
    "                temp_number = int(i)\n",
    "                stack.append(temp_number)\n",
    "            except ValueError:\n",
    "                right_number = stack.pop()\n",
    "                left_number = stack.pop()\n",
    "                if i == \"+\":\n",
    "                    temp_value = left_number + right_number\n",
    "                elif i == \"-\":\n",
    "                    temp_value = left_number - right_number\n",
    "                elif i == \"*\":\n",
    "                    temp_value = left_number * right_number\n",
    "                elif i == \"/\":\n",
    "                    temp_value = int(left_number / right_number)\n",
    "                stack.append(temp_value)\n",
    "        return int(stack.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        \"\"\"\n",
    "        :type tokens: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack1, stack2 = [], []\n",
    "        for i in range(len(tokens) - 1, -1, -1):\n",
    "            stack1.append(tokens[i])\n",
    "        operateset = set([\"+\", \"-\", \"*\", \"/\"])\n",
    "        while stack1:\n",
    "            top = stack1.pop()\n",
    "            if top in operateset:\n",
    "                num1, num2 = stack2.pop(), stack2.pop()\n",
    "                stack2.append(self.operate(top, num1, num2))\n",
    "            else:\n",
    "                stack2.append(int(top))\n",
    "        return stack2[-1]\n",
    "\n",
    "    def operate(self, op, num1, num2):\n",
    "        if op == \"+\":\n",
    "            return num2 + num1\n",
    "        if op == \"-\":\n",
    "            return num2 - num1\n",
    "        if op == \"*\":\n",
    "            return num2 * num1\n",
    "        if op == \"/\":\n",
    "            return int(num2 / num1) if  num1 !=0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        \"\"\"\n",
    "        :type tokens: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not tokens:\n",
    "            return None\n",
    "\n",
    "\n",
    "        def operate(right, left, oper):\n",
    "            if oper == \"+\":\n",
    "                return int(left + right)\n",
    "            if oper == \"-\":\n",
    "                return int(left - right)\n",
    "            if oper == \"*\":\n",
    "                return int(left * right)\n",
    "            if oper == \"/\":\n",
    "                return int(left / right)\n",
    "\n",
    "\n",
    "        stack = []\n",
    "        while tokens:\n",
    "            token = tokens.pop(0)\n",
    "            if token in [\"+\", \"-\", \"*\", \"/\"]:\n",
    "                stack.append(operate(stack.pop(), stack.pop(), token))\n",
    "            else:\n",
    "                stack.append(int(token))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        \"\"\"\n",
    "        :type tokens: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #这里\"/\"理解为'//'\n",
    "        stack=[]\n",
    "        re=0\n",
    "        for x in tokens:\n",
    "            if x in \"-+*/\":\n",
    "                if x=='+':\n",
    "                    stack.append(stack.pop()+stack.pop())\n",
    "                elif x=='-':\n",
    "                    stack.append(-stack.pop()+stack.pop())\n",
    "                elif x=='*':\n",
    "                    stack.append(stack.pop()*stack.pop())\n",
    "                else:\n",
    "                    x=stack.pop()\n",
    "                    y=stack.pop()\n",
    "                    t=y//x\n",
    "                    if t*x==y:\n",
    "                        stack.append(t)\n",
    "                    else:\n",
    "                        if t>=0:\n",
    "                            stack.append(t)\n",
    "                        else:\n",
    "                            stack.append(t+1)\n",
    "            else:\n",
    "                stack.append(int(x))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        \"\"\"\n",
    "        :type tokens: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not tokens:\n",
    "            return None\n",
    "\n",
    "\n",
    "        def operate(right, left, oper):\n",
    "            if oper == \"+\":\n",
    "                return int(left + right)\n",
    "            if oper == \"-\":\n",
    "                return int(left - right)\n",
    "            if oper == \"*\":\n",
    "                return int(left * right)\n",
    "            if oper == \"/\":\n",
    "                return int(left / right)\n",
    "\n",
    "\n",
    "        stack = []\n",
    "        while tokens:\n",
    "            token = tokens.pop(0)\n",
    "            if token in [\"+\", \"-\", \"*\", \"/\"]:\n",
    "                middle = operate(stack.pop(), stack.pop(), token)\n",
    "                stack.append(middle)\n",
    "            else:\n",
    "                stack.append(int(token))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        \"\"\"\n",
    "        :type tokens: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack = [];\n",
    "        for t in tokens:\n",
    "            if((t[0] == '-' and t[1:].isalnum()) or t.isalnum()):\n",
    "                stack.append(int(t));\n",
    "            else:\n",
    "                b = stack.pop()\n",
    "                a = stack.pop()\n",
    "                print (a,b)\n",
    "                if(t == '+'):\n",
    "                    stack.append(a+b);\n",
    "                if(t == '-'):\n",
    "                    stack.append(a-b);\n",
    "                if(t == '/'):\n",
    "                    stack.append(int(a/b))\n",
    "                if(t == '*'):\n",
    "                    stack.append(a*b);\n",
    "        return stack[0];\n",
    "    \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens):\n",
    "        \"\"\"\n",
    "        :type tokens: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l=[]\n",
    "        fh=['+','-','*','/']\n",
    "        for i in tokens:\n",
    "            if i not in fh:\n",
    "                l.append(i)\n",
    "            else:\n",
    "                a=l.pop()\n",
    "                b=l.pop()\n",
    "                c=int(eval(b+i+a))\n",
    "                print(a+i+b,a,b,c)\n",
    "                l.append(str(c))\n",
    "        return int(l[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import operator\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: 'List[str]') -> 'int':\n",
    "        nums, ops = [], []\n",
    "        table = {\n",
    "            \"+\": operator.add,\n",
    "            \"-\": operator.sub,\n",
    "            \"*\": operator.mul,\n",
    "            \"/\": operator.truediv\n",
    "        }\n",
    "        for item in tokens:\n",
    "            if item not in table:\n",
    "                nums.append(int(item))\n",
    "                continue\n",
    "            else:\n",
    "                op = table[item]\n",
    "            right = nums.pop(-1)\n",
    "            left = nums.pop(-1)\n",
    "            res = int(op(left, right))\n",
    "            nums.append(res)\n",
    "        \n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "    \n",
    "        op = {\"+\", \"-\", \"*\", \"/\"}\n",
    "        for t in tokens:\n",
    "            if t not in op:\n",
    "                stack.append(t)\n",
    "            else:\n",
    "                r = int(stack.pop())\n",
    "                l = int(stack.pop())\n",
    "                if t == \"+\":\n",
    "                    stack.append(r + l)\n",
    "                elif t == \"-\":\n",
    "                    stack.append(l - r)\n",
    "                elif t == \"*\":\n",
    "                    stack.append(l * r)\n",
    "                elif t == \"/\":\n",
    "                    if l * r < 0:\n",
    "                        stack.append(- (abs(l)//abs(r)))\n",
    "                    else:\n",
    "                        stack.append(abs(l) // abs(r))\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        length = len(tokens)\n",
    "        if length <= 2:\n",
    "            return tokens[0]\n",
    "\n",
    "        def calc(num1, num2, operator):\n",
    "            num1, num2 = int(num1), int(num2)\n",
    "            if operator == '+':\n",
    "                return num1 + num2\n",
    "            elif operator == '-':\n",
    "                return num1 - num2\n",
    "            elif operator == '*':\n",
    "                return num1 * num2\n",
    "            elif operator == '/':\n",
    "                return int(num1 / num2)\n",
    "\n",
    "        while length > 1:\n",
    "            i = 0\n",
    "            while i < length:\n",
    "                if not tokens[i].isdigit() and len(tokens[i]) == 1:\n",
    "                    index = i - 2\n",
    "                    num1 = tokens.pop(index)\n",
    "                    num2 = tokens.pop(index)\n",
    "                    operator = tokens.pop(index)\n",
    "                    tokens.insert(index, str(calc(num1, num2, operator)))\n",
    "                    length -= 2\n",
    "                    break\n",
    "                i += 1\n",
    "        return int(tokens[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        l=[]\n",
    "        for i in tokens:\n",
    "            if i=='+':\n",
    "                l.append(l.pop().__radd__(l.pop()))\n",
    "            elif i=='-':\n",
    "                l.append(l.pop().__rsub__(l.pop()))\n",
    "            elif i=='*':\n",
    "                l.append(l.pop().__rmul__(l.pop()))\n",
    "            elif i=='/':\n",
    "                l.append(int(l.pop().__rtruediv__(l.pop())))\n",
    "            else:\n",
    "                l.append(int(i))\n",
    "                \n",
    "        return l[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        if not tokens:\n",
    "            return 0\n",
    "        stack = []\n",
    "        while tokens:\n",
    "            word = tokens.pop()\n",
    "            stack.append(word)\n",
    "            while len(stack) > 1 and (stack[-1].isdigit() or len(stack[-1]) > 1) and (stack[-2].isdigit() or len(stack[-2]) > 1):\n",
    "                word1 = stack.pop()\n",
    "                word2 = stack.pop()\n",
    "                operator = stack.pop()\n",
    "                if operator == \"+\":\n",
    "                    word3 = int(word1) + int(word2)\n",
    "                elif operator == \"-\":\n",
    "                    word3 = int(word1) - int(word2)\n",
    "                elif operator == \"*\":\n",
    "                    word3 = int(word1) * int(word2)\n",
    "                elif operator == \"/\":\n",
    "                    word3 = abs(int(word1)) // abs(int(word2))\n",
    "                    if int(word1) * int(word2) < 0:\n",
    "                        word3 = 0 - word3\n",
    "                stack.append(str(word3))               \n",
    "        return int(stack[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "\n",
    "        stack = []\n",
    "        top = 0  # len of stack\n",
    "\n",
    "        for token in tokens:\n",
    "            if (token == \"+\"):\n",
    "                stack[top - 2] = stack[top - 2] + stack[top - 1]\n",
    "                top = top - 1\n",
    "                stack = stack[:top]\n",
    "            elif (token == \"-\"):\n",
    "                stack[top - 2] = stack[top - 2] - stack[top - 1]\n",
    "                top = top - 1\n",
    "                stack = stack[:top]\n",
    "            elif (token == \"*\"):\n",
    "                stack[top - 2] = stack[top - 2] * stack[top - 1]\n",
    "                top = top - 1\n",
    "                stack = stack[:top]\n",
    "            elif (token == \"/\"):\n",
    "                stack[top - 2] = int(stack[top - 2] / stack[top - 1])\n",
    "                top = top - 1\n",
    "                stack = stack[:top]\n",
    "            else:\n",
    "                stack.append(int(token))\n",
    "                top = top + 1\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens) -> int:\n",
    "        #  适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果\n",
    "        #  压入栈中。注意，除法只取整数，可以用int()实现\n",
    "        if len(tokens)==1:\n",
    "            return int(tokens[0])\n",
    "        stack = []\n",
    "        for i in range(len(tokens)):\n",
    "            if tokens[i] in ['+','-','*','/']:\n",
    "                b = stack.pop()\n",
    "                a = stack.pop()\n",
    "                res = int(eval(a + tokens[i] + b))\n",
    "                stack.append(str(res))\n",
    "            else:\n",
    "                stack.append(tokens[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            if token == '+':\n",
    "                stack.append(stack.pop() + stack.pop())\n",
    "            elif token == '-':\n",
    "                temp = stack.pop()\n",
    "                stack.append(stack.pop() - temp)\n",
    "            elif token == '*':\n",
    "                stack.append(stack.pop() * stack.pop())\n",
    "            elif token == '/':\n",
    "                temp = stack.pop()\n",
    "                stack.append(int(stack.pop() / temp))\n",
    "            else:\n",
    "                stack.append(int(token))\n",
    "        return stack[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        symbols = {\"+\": \"+\", \"-\": \"-\",\"*\": \"*\", \"/\": \"/\"}\n",
    "        queue = []\n",
    "        for ele in tokens:\n",
    "            if symbols.get(ele, None):\n",
    "                left = queue.pop()\n",
    "                right = queue.pop()\n",
    "                print(right + symbols[ele] + left)\n",
    "                res = eval(right + symbols[ele] + left)\n",
    "                queue.append(str(int(res)))\n",
    "            else:\n",
    "                queue.append(ele)\n",
    "        \n",
    "        return int(queue.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from ast import literal_eval\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        result = 0\n",
    "        arithmetic_signs = {'+', '-', '*', '/'}\n",
    "        for char in tokens:\n",
    "            if char in arithmetic_signs:\n",
    "                right = int(stack.pop())\n",
    "                left = int(stack.pop())\n",
    "                if char == '+':\n",
    "                    result = left + right\n",
    "                elif char == '-':\n",
    "                    result = left - right\n",
    "                elif char == '*':\n",
    "                    result = left * right\n",
    "                elif char == '/':\n",
    "                    result = int(left / right)\n",
    "                stack.append(result)\n",
    "            else:\n",
    "                stack.append(char)\n",
    "        return int(stack[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        def cal(operand2, operand1, operator):\n",
    "            print(operand1, operator, operand2)\n",
    "            if operator == '+':\n",
    "                return operand1 + operand2\n",
    "            elif operator == '-':\n",
    "                return operand1 - operand2\n",
    "            elif operator == '*':\n",
    "                return operand1 * operand2\n",
    "            elif operator == '/':\n",
    "                return int(operand1 / operand2)\n",
    "            else:\n",
    "                raise ValueError(\"Invalid operator: {}\".format(operator))\n",
    "\n",
    "        stack = []\n",
    "        for token in tokens:\n",
    "            try:\n",
    "                operand = int(token)\n",
    "            except:\n",
    "                try:\n",
    "                    operand2 = stack.pop(-1)\n",
    "                    operand1 = stack.pop(-1)\n",
    "                    stack.append(cal(operand2, operand1, token))\n",
    "                except Exception as e:\n",
    "                    print(e)\n",
    "                    print(stack)\n",
    "            else:\n",
    "                stack.append(operand)\n",
    "        assert len(stack) == 1, str(stack)\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "\n",
    "        def calculate(token, num1, num2):\n",
    "            if token == '+':\n",
    "                return float(num1) + float(num2)\n",
    "            if token == '-':\n",
    "                return float(num1) - float(num2)\n",
    "            if token == '*':\n",
    "                return float(num1) * float(num2)\n",
    "            if token == '/':\n",
    "                return float(num1) / float(num2)\n",
    "        \n",
    "        token_set = set(['+', '-', '*', '/'])\n",
    "        i = 2\n",
    "        while i < len(tokens):\n",
    "            if tokens[i] in token_set:\n",
    "                ans = calculate(tokens[i], tokens[i-2], tokens[i-1])\n",
    "                tokens[i] = str(int(ans))\n",
    "                tokens.pop(i-1)\n",
    "                tokens.pop(i-2)\n",
    "                i = 1\n",
    "            i += 1\n",
    "        return int(tokens[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        num_stack = []\n",
    "        op_set = (['+', '-', '*', '/'])\n",
    "        while tokens:\n",
    "            val = tokens.pop(0)\n",
    "            if val not in op_set: \n",
    "                num_stack.append(val)\n",
    "            elif len(num_stack) >= 2:\n",
    "                num2 = num_stack.pop()\n",
    "                num1 = num_stack.pop()\n",
    "                s = num1 + val + num2\n",
    "                num_stack.append(str(int(eval(s))))\n",
    "        return int(num_stack[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        if len(tokens) == 1:return int(tokens[0])\n",
    "\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i < len(tokens):\n",
    "            if tokens[i] not in ('+','-','*','/'):\n",
    "                i += 1\n",
    "            elif tokens[i] == '+':\n",
    "                ans = int(tokens[i-2])+int(tokens[i-1])\n",
    "                tokens[i-2:i+1] = [ans]\n",
    "                i -= 2\n",
    "            elif tokens[i] == '-':\n",
    "                ans = int(tokens[i-2])-int(tokens[i-1])\n",
    "                tokens[i-2:i+1] = [ans]\n",
    "                i -= 2\n",
    "            elif tokens[i] == '*':\n",
    "                ans = int(tokens[i-2])*int(tokens[i-1])\n",
    "                tokens[i-2:i+1] = [ans]\n",
    "                i -= 2\n",
    "            elif tokens[i] == '/':\n",
    "                ans = int(tokens[i-2])/int(tokens[i-1])\n",
    "                tokens[i-2:i+1] = [ans]\n",
    "                i -= 2\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        def judge_num(num):\n",
    "            if len(num)>1 and num[0]=='-':\n",
    "                return str.isdigit(num[1:])\n",
    "            else:\n",
    "                return str.isdigit(num)\n",
    "        i = 0\n",
    "        while len(tokens)>1:\n",
    "            #print(tokens)\n",
    "            if judge_num(tokens[i]):\n",
    "                i+=1\n",
    "                continue\n",
    "            else:\n",
    "                #print(tokens[i-2]+tokens[i]+tokens[i-1])\n",
    "                if tokens[i] == '+':\n",
    "                    temp_result = int(tokens[i-2])+int(tokens[i-1])\n",
    "                elif tokens[i] == '-':\n",
    "                    temp_result = int(tokens[i-2])-int(tokens[i-1])\n",
    "                elif tokens[i] == '*':\n",
    "                    temp_result = int(tokens[i-2])*int(tokens[i-1])\n",
    "                elif tokens[i] == '/':\n",
    "                    temp_result = int(tokens[i-2])/int(tokens[i-1])\n",
    "                else:\n",
    "                    return\n",
    "                tokens.pop(i)\n",
    "                tokens.pop(i-1)\n",
    "                tokens.pop(i-2)\n",
    "                tokens.insert(i-2,str(int(temp_result)))\n",
    "                i = i-1\n",
    "        return int(tokens[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        n=len(tokens)\n",
    "        i=0\n",
    "        while n!=1:\n",
    "            while i<n and tokens[i] not in '+-*/':i+=1\n",
    "            if tokens[i]=='*':\n",
    "                tokens[i-2]=int(tokens[i-2])*int(tokens[i-1])\n",
    "            elif tokens[i]=='/':\n",
    "                tokens[i-2]=int(int(tokens[i-2])/int(tokens[i-1]))\n",
    "            elif tokens[i]=='-':\n",
    "                tokens[i-2]=int(tokens[i-2])-int(tokens[i-1])\n",
    "            elif tokens[i]=='+':\n",
    "                tokens[i-2]=int(tokens[i-2])+int(tokens[i-1])\n",
    "            tokens.pop(i-1)\n",
    "            tokens.pop(i-1)\n",
    "            i-=1\n",
    "            n-=2\n",
    "        return int(tokens[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack=[]\n",
    "\n",
    "        for token in tokens:\n",
    "            if token not in {'+','-','*','/'}:\n",
    "                stack.append(int(token))   \n",
    "            else:\n",
    "                num1=stack.pop()\n",
    "                num2=stack.pop()            \n",
    "                if token == '+': \n",
    "                    stack.append(num2+num1)\n",
    "                if token == '-': \n",
    "                    stack.append(num2-num1)\n",
    "                if token == '*': \n",
    "                    stack.append(num2*num1)\n",
    "                if token == '/': \n",
    "                    stack.append(int(num2/num1))\n",
    "                \n",
    "        return stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        bank = collections.deque()\n",
    "        res = None\n",
    "        l=len(tokens)\n",
    "        if l == 1:\n",
    "            return int(tokens[0])\n",
    "        i = 0\n",
    "        while i<l:\n",
    "            #print(bank,res)\n",
    "            if tokens[i] == '+':\n",
    "                a = bank.pop()\n",
    "                b = bank.pop()\n",
    "                res = b+a\n",
    "                bank.append(res)\n",
    "            elif tokens[i] == '-':\n",
    "                a = bank.pop()\n",
    "                b = bank.pop()\n",
    "                res = b-a\n",
    "                bank.append(res)\n",
    "            elif tokens[i] == '*':\n",
    "                a = bank.pop()\n",
    "                b = bank.pop()\n",
    "                res = b*a\n",
    "                bank.append(res)\n",
    "            elif tokens[i] == '/':\n",
    "                a = bank.pop()\n",
    "                b = bank.pop()\n",
    "                res = int(b/a)\n",
    "                bank.append(res)\n",
    "            else:\n",
    "                bank.append(int(tokens[i]))\n",
    "            i+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        S = set(['+', '-', '*', '/'])\n",
    "        for token in tokens:\n",
    "            if token not in S:\n",
    "                stack.append(int(token))\n",
    "            else:\n",
    "                r, l = stack.pop(), stack.pop()\n",
    "                calc = None\n",
    "                if token == '+':\n",
    "                    calc = l + r\n",
    "                elif token == '-':\n",
    "                    calc = l - r\n",
    "                elif token == '*':\n",
    "                    calc = l * r\n",
    "                else:\n",
    "                    calc = int(l / r)\n",
    "                stack.append(calc)\n",
    "        return stack[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        i=2\n",
    "        while i<len(tokens):\n",
    "            if tokens[i]=='+' :\n",
    "                tokens[i-2]=int(tokens[i-2])+int(tokens[i-1])\n",
    "                tokens.pop(i-1)\n",
    "                tokens.pop(i-1)\n",
    "                i=i-1\n",
    "            elif tokens[i]=='-':\n",
    "                tokens[i-2]=int(tokens[i-2])-int(tokens[i-1])\n",
    "                tokens.pop(i-1)\n",
    "                tokens.pop(i-1)\n",
    "                i=i-1\n",
    "            elif tokens[i]=='*':\n",
    "                tokens[i-2]=int(tokens[i-2])*int(tokens[i-1])\n",
    "                tokens.pop(i-1)\n",
    "                tokens.pop(i-1)\n",
    "                i=i-1\n",
    "            elif tokens[i]=='/':\n",
    "                tokens[i-2]=int(int(tokens[i-2])/int(tokens[i-1]))\n",
    "                tokens.pop(i-1)\n",
    "                tokens.pop(i-1)\n",
    "                i=i-1\n",
    "            else:\n",
    "                i=i+1\n",
    "        return int(tokens[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        operator = {'+', '-', '*', '/'}\n",
    "        while len(tokens)>1:\n",
    "            for i in range(2, len(tokens)):\n",
    "                if tokens[i] in operator:\n",
    "                    if tokens[i] == '+':\n",
    "                        tokens[i] = int(tokens[i-2])+int(tokens[i-1])\n",
    "                    if tokens[i] == '-':\n",
    "                        tokens[i] = int(tokens[i-2])-int(tokens[i-1])\n",
    "                    if tokens[i] == '*':\n",
    "                        tokens[i] = int(tokens[i-2])*int(tokens[i-1])\n",
    "                    if tokens[i] == '/':\n",
    "                        tokens[i] = int(int(tokens[i-2])/int(tokens[i-1]))\n",
    "                    tokens.pop(i-1)\n",
    "                    tokens.pop(i-2)\n",
    "                    break\n",
    "        return int(tokens[0])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        for i in tokens:\n",
    "            try:\n",
    "                stack.append(int(i))\n",
    "            except:\n",
    "                num2 = stack.pop()\n",
    "                num1 = stack.pop()\n",
    "                stack.append(self.op(num1, num2, i))\n",
    "        return stack[0]\n",
    "    \n",
    "    def op(self, num1, num2, operator):\n",
    "        \n",
    "        if operator == \"+\": return num1 + num2\n",
    "        \n",
    "        elif operator == \"-\": return num1 - num2\n",
    "\n",
    "        elif operator == \"*\": return num1 * num2\n",
    "\n",
    "        elif operator == \"/\": return int(num1 / float(num2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evalRPN(self, tokens: List[str]) -> int:\n",
    "        stack = []\n",
    "        plus = lambda a, b : b + a\n",
    "        sub = lambda a, b: b - a\n",
    "        mul = lambda a, b: b * a\n",
    "        div = lambda a, b: int(b / a)\n",
    "        opt = {\n",
    "            \"+\": plus,\n",
    "            \"-\": sub,\n",
    "            \"*\": mul,\n",
    "            \"/\": div\n",
    "        }\n",
    "        for t in tokens:\n",
    "            if t in opt:\n",
    "                stack.append(opt[t](stack.pop(), stack.pop()))\n",
    "            else:\n",
    "                stack.append(int(t))\n",
    "        return stack.pop()\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
